import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution494 {

    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer,Integer>[] dp = new Map[nums.length];
        dp[0]=new HashMap<>();
        dp[0].put(nums[0],dp[0].getOrDefault(nums[0],0)+1);
        dp[0].put(-nums[0],dp[0].getOrDefault(-nums[0],0)+1);

        for (int i = 1; i < nums.length; i++) {
            dp[i]=new HashMap<>();
            Map<Integer,Integer> tmpMap=dp[i];
            Map<Integer,Integer> lastMap=dp[i-1];
            int tmpNum=nums[i];
            for (Map.Entry et:lastMap.entrySet()) {
                int num=(Integer) et.getKey();
                int count=(Integer) et.getValue();
                tmpMap.put(num+tmpNum,tmpMap.getOrDefault(num+tmpNum,0)+count);
                tmpMap.put(num-tmpNum,tmpMap.getOrDefault(num-tmpNum,0)+count);
            }
        }
        return dp[nums.length-1].getOrDefault(target,0);
    }

    public static void main(String[] args) {
        Solution494 s=new Solution494();
        System.out.println(s.findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1},1));
    }
}
